To raise the material utilization ratio of heuristic nesting for irregular shapes, a Gravity No-Fit-Polygon (NFP) and Edge Fitness-based Heuristic Nesting Algorithm (GEFHNA) was proposed. Firstly, the definition of Edge Fitness (EF) to measure the fitness between the material and irregular shape produced in the process of packing was defined, and a packing strategy combining Gravity NFP (GNFP) with edge fitness was proposed to reduce the area of gap generated in packing. Secondly, a Weiler-Atherton-based algorithm was presented to compute remained materials and add holes produced in each round of packing to the list of materials. The heuristic packing algorithm prefered the holes in next rounds of packing to reduce proportion of holes in released layout. Finally, a heuristic algorithm based on the previous packing strategy and reuse strategy was put forward and the comparison experiments of GEFHNA with intelligent algorithm and similar softwares were presented. Experimental results on benchmarks provided by ESICUP (EURO Special Interest Group on Cutting and Packing) show that GEFHNA only has about 1/1000 time consumption of intelligent algorithm-based nesting scheme and achieves 7/11 relatively optimal utilization rate in contrast with two commercial softwares NestLib and SigmaNest.